package javax;

public class Xp_0108 {
    //归并扩展
    //求小和问题 4 1 3 5 0 6 求每个数左边比他小的数累加起来  暴力解O（n2）
    //归并排序
    public static void mergeSort(int[] arr){
        if (arr == null || arr.length<2){
            return;
        }
    }
    //归并排序
    public static void sort(int[] arr,int L ,int R){
        if( L==R){
            return;
        }
        int mid = L + (R-L)/2;//L + ((R +　Ｌ)　>>　１)
        sort(arr,L,mid);
        sort(arr,mid+1,R);
        merge(arr,L,mid,R);
    }
    //合并外排
    public static void merge(int[] arr,int L ,int m,int R) {
        //help 长度为L到R
        int[] help = new int[R - L + 1];
        //辅助数组起点
        int i = 0;
        //p两边开始的位置
        int p1 = i;
        int p2 = m + 1;
        int res = 0;
        //在对应范围内，都还没越界
        while (p1 <= m && p2 < R) {
            res += arr[p1] < arr[p2] ? (R - p2 + 1) * arr[p1] : 0;
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        //两个必有且只有一个越界
        while (p1 <= m) {
            help[i++] = arr[p1++];
        }
        while (p2 < R) {
            help[i++] = arr[p2++];
        }
        //拷贝回原数组
        for (i = 0; i < help.length; i++) {
            arr[L + i] = help[i];
        }
    }
}
